Oracle machine

Given a function $f$ to minimize and a convex constraint set $\mathcal{S}$, assume we have:

• Function oracle: Evaluate $f(\mathbf{x})$ for any $\mathbf{x}$.
• Gradient oracle: Evaluate $∇f(\mathbf{x})$ for any $\mathbf{x}$.
• Projection oracle: Evaluate $P_\mathcal{S} (\mathbf{x})$ for any $\mathbf{x}$.
• Separation oracle

References:

1. https://en.wikipedia.org/wiki/Oracle_machine